package com.qt.leetcode;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

public class Demo01 {
    /**  1090. 受标签影响的最大值
     * 我们有一个n项的集合。给出两个整数数组values和 labels，第 i 个元素的值和标签分别是values[i]和labels[i]。还会给出两个整数numWanted和 useLimit 。
     *
     * 从 n 个元素中选择一个子集 s :
     *
     * 子集 s 的大小小于或等于 numWanted 。
     * s 中 最多 有相同标签的 useLimit 项。
     * 一个子集的分数是该子集的值之和。
     *
     * 返回子集s 的最大 分数 。

     * 示例 1：
     *
     * 输入：values = [5,4,3,2,1], labels = [1,1,2,2,3], numWanted = 3, useLimit = 1
     * 输出：9
     * 解释：选出的子集是第一项，第三项和第五项。
     * 示例 2：
     *
     * 输入：values = [5,4,3,2,1], labels = [1,3,3,3,2], numWanted = 3, useLimit = 2
     * 输出：12
     * 解释：选出的子集是第一项，第二项和第三项。
     * 示例 3：
     *
     * 输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], numWanted = 3, useLimit = 1
     * 输出：16
     * 解释：选出的子集是第一项和第四项。
     *
     * 提示：
     * n == values.length == labels.length
     * 1 <= n <= 2 * 104
     * 0 <= values[i], labels[i] <= 2 * 104
     * 1 <= numWanted, useLimit <= n
     */

    public static int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
        int n = values.length;
        int[][] infos = new int[n][2];
        int maxLabel = 0;
        for (int i = 0; i < infos.length; i++) {
            infos[i][0] = values[i];
            infos[i][1] = labels[i];
            maxLabel = Math.max(maxLabel, labels[i]);
        }
        Arrays.sort(infos, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[0] - o1[0];
            }
        });

        /*
        核心参数：
        1.   相同标签（最大标签数） sameLabelNum == useLimit
        2.   签个数（最多numWanted个）  maxLabelNum == numWanted;
        3.  分数  scope
         */
        //int sameLabelNum = 0;//相同标签数
        int maxLabelNum = 0;//签个数
        int scope = 0;//最大分数
        int[] labelCount = new int[maxLabel + 1];//标签值统计数组
        for (int i = 0; i < infos.length; i++) {
            if(maxLabelNum == numWanted){
                break;
            }
            if( labelCount[infos[i][1]] == useLimit){
                continue;
            }
            scope += infos[i][0];//分数累计
            labelCount[infos[i][1]]++;//对应标签数量累计
            maxLabelNum++;//总签个数累计

        }



        return scope;
    }

    public static int largestValsFromLabelsGf(int[] values, int[] labels, int numWanted, int useLimit) {
        int n = values.length;
        Integer[] id = new Integer[n];
        for (int i = 0; i < n; i++) {
            id[i] = i;
        }
        Arrays.sort(id, new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                return values[b] - values[a];
            }
        });

        int ans = 0, choose = 0;
        Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
        for (int i = 0; i < n && choose < numWanted; ++i) {
            //int label = labels[id[i]];
            int label = labels[i];
            if (cnt.getOrDefault(label, 0) == useLimit) {
                continue;
            }
            ++choose;
            //ans += values[id[i]];
            ans += values[i];
            cnt.put(label, cnt.getOrDefault(label, 0) + 1);
        }
        return ans;
    }


    public static void main(String[] args) {
//        int[] values = {8,8,7,6,9};
//        int[] labels = {0,0,0,1,1};
//        int numWanted = 3;
//        int useLimit = 1;
//        //int i = largestValsFromLabels(values, labels, numWanted, useLimit);
//        int i = largestValsFromLabelsGf(values, labels, numWanted, useLimit);
//        System.out.println(i);
        int[] nums = {2,5,5,11};
        int target = 10;
        int[] ints = twoSum(nums, target);
        System.out.println(ints[0] + "," + ints[1]);
    }

    public static int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        for(int i = 0;i < nums.length - 1;i++){
            for (int j = 0; j < nums.length; j++) {
                if(i != j && nums[i] + nums[j] == target){
                    res[0] = i;
                    res[1] = j;
                    return res;
                }
            }
        }
        return res;

    }

    public static int[] twoSumPlus(int[] nums, int target) {

        HashMap<Integer, Integer> item = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {

            if(item.containsKey(nums[i])){
                return new int[]{item.get(nums[i]),i};
            }
            item.put(target - nums[i],i);
        }


        return new int[999];

    }

}